{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Special Array With X Elements Greater Than or Equal X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: specialArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特殊数组的特征值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数数组 <code>nums</code> 。如果存在一个数 <code>x</code> ，使得 <code>nums</code> 中恰好有 <code>x</code> 个元素 <strong>大于或者等于</strong> <code>x</code> ，那么就称 <code>nums</code> 是一个 <strong>特殊数组</strong> ，而 <code>x</code> 是该数组的 <strong>特征值</strong> 。</p>\n",
    "\n",
    "<p>注意： <code>x</code> <strong>不必</strong> 是 <code>nums</code> 的中的元素。</p>\n",
    "\n",
    "<p>如果数组 <code>nums</code> 是一个 <strong>特殊数组</strong> ，请返回它的特征值 <code>x</code> 。否则，返回<em> </em><code>-1</code> 。可以证明的是，如果 <code>nums</code> 是特殊数组，那么其特征值 <code>x</code> 是 <strong>唯一的</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,5]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有 2 个元素（3 和 5）大于或等于 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,0]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>没有满足题目要求的特殊数组，故而也不存在特征值 x 。\n",
    "如果 x = 0，应该有 0 个元素 &gt;= x，但实际有 2 个。\n",
    "如果 x = 1，应该有 1 个元素 &gt;= x，但实际有 0 个。\n",
    "如果 x = 2，应该有 2 个元素 &gt;= x，但实际有 0 个。\n",
    "x 不能取更大的值，因为 nums 中只有两个元素。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,4,3,0,4]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>有 3 个元素大于或等于 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,6,7,7,0]\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [special-array-with-x-elements-greater-than-or-equal-x](https://leetcode.cn/problems/special-array-with-x-elements-greater-than-or-equal-x/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [special-array-with-x-elements-greater-than-or-equal-x](https://leetcode.cn/problems/special-array-with-x-elements-greater-than-or-equal-x/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,5]', '[0,0]', '[0,4,3,0,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        \n",
    "        if 0 > nums[0]:\n",
    "            return 0\n",
    "        \n",
    "        for x in range(1, len(nums)):\n",
    "            if nums[x - 1] >= x > nums[x]:\n",
    "                return x\n",
    "            \n",
    "        if nums[-1] >= len(nums):\n",
    "            return len(nums)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort(reverse=True)\n",
    "        for i in range(1,n+1):\n",
    "            if nums[i-1]>=i and (i==n or nums[i]<i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n_nums = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n_nums):\n",
    "            if nums[-(i+1)] >= (1+ i):\n",
    "                if i == n_nums -1 or nums[-(i+2)] < (i + 1):\n",
    "                    return i + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        len_nums = len(nums)\n",
    "        sort_nums = sorted(nums , reverse = True)\n",
    "        if sort_nums[-1] >= len_nums:   # 满足最开始给的类似[3, 5]信息\n",
    "            return len_nums\n",
    "        for i in range(1, len_nums):  # 一次遍历\n",
    "            if sort_nums[i - 1] >= i and sort_nums[i] < i:\n",
    "                return i\n",
    "        return -1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums)):\n",
    "            if i-1>0:\n",
    "                if nums[i]>=len(nums)-i and nums[i-1]<len(nums)-i:\n",
    "                    return len(nums[i:])\n",
    "            else:\n",
    "                if nums[i]>=len(nums)-i:\n",
    "                    return len(nums[i:])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        sum=0\n",
    "        a=max(nums)\n",
    "        if a<1:\n",
    "            return -1\n",
    "        for i in range(1,a+1):\n",
    "            sum=0\n",
    "            for num in nums:\n",
    "                if num>=i:\n",
    "                    sum+=1\n",
    "            if sum==i:\n",
    "                return sum\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums) + 1):\n",
    "            sum = 0\n",
    "            for n in nums:\n",
    "                if n >= i:\n",
    "                    sum += 1\n",
    "                    if sum > i:\n",
    "                        break\n",
    "            if sum == i:\n",
    "                return sum\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(n + 1):\n",
    "            cnt = 0\n",
    "            for x in nums:\n",
    "                if x >= i:\n",
    "                    cnt += 1\n",
    "            print('i=', i)\n",
    "            print('cnt=',cnt)\n",
    "            if i == cnt:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= i + 1 and (i == n - 1 or nums[i + 1] < i + 1):\n",
    "                return i + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums) + 1):\n",
    "            sum = 0\n",
    "            for n in nums:\n",
    "                if n >= i:\n",
    "                    sum += 1\n",
    "            if sum == i:\n",
    "                return sum\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        b = 0\n",
    "        c = 0\n",
    "        for i in range(1, len(nums)+1):\n",
    "            a = 0    \n",
    "            for j in nums:\n",
    "                if j >= i:\n",
    "                    a += 1\n",
    "            if a == i:\n",
    "                b+=1\n",
    "                c = a\n",
    "        if b == 1:\n",
    "            return c\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if nums[len(nums)-i] >= i and (i == len(nums) or nums[len(nums)-i-1] < i):\n",
    "                return i\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums) + 1):\n",
    "            sum = 0\n",
    "            for n in nums:\n",
    "                if n >= i:\n",
    "                    sum += 1\n",
    "            if sum == i:\n",
    "                return sum\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if nums == None:\n",
    "            return -1\n",
    "        for i in range(len(nums)-1, 0, -1):\n",
    "            if nums[i] >= len(nums)-i and nums[i-1] < len(nums)-i:\n",
    "                return len(nums)-i\n",
    "        if nums[0] >= len(nums):\n",
    "            return len(nums)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for x in range(len(nums)+1,0,-1):\n",
    "            a = 0\n",
    "            for i in nums:\n",
    "                if i >= x:\n",
    "                    a += 1\n",
    "            if a == x:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        total = 0\n",
    "        m = max(nums) + 1\n",
    "        for x in range(0,m):\n",
    "            for j in nums:\n",
    "                if x <= j:\n",
    "                    total +=1\n",
    "            if total == x:\n",
    "                return x\n",
    "            total = 0\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(1, n+1):\n",
    "            index = bisect.bisect_left(nums, i)\n",
    "            if i == (n-index):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def specialArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        nums_set = set(nums)\n",
    "        sort_list = sorted(nums)\n",
    "        for i in nums_set:\n",
    "            si = sort_list.index(i)\n",
    "            x = length - si\n",
    "            if si == 0 and x <= i:\n",
    "                return x\n",
    "            if sort_list[si-1] < x <= i:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] >= i and ( i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= n - i and (i == 0 or nums[i - 1] < n - i):\n",
    "                return n - i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if len([k for k in nums if k >= i]) == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        a = 0\n",
    "        lst = []\n",
    "        while a < max(nums) + 1:\n",
    "            c = 0\n",
    "            for i in nums:\n",
    "                if i >= a:\n",
    "                    c += 1\n",
    "            if c == a:\n",
    "                return a\n",
    "            else:\n",
    "                a += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        for i in range(1, length + 1):\n",
    "            if sum(i <= j for j in nums) == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "         l = len(nums)\n",
    "         \n",
    "        \n",
    "         nums.sort()\n",
    "         if l < nums[0]:\n",
    "             return l\n",
    "\n",
    "         for i in range(len(nums)):\n",
    "              if nums[i] == 0:\n",
    "                 continue\n",
    "              elif i > 0 and l - i <= nums[i] and l - i > nums[i - 1]:\n",
    "                    return l - i\n",
    "              elif i == 0 and l - i == nums[i]:\n",
    "                  return l - i\n",
    "                                  \n",
    "         return -1\n",
    "         \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "         l = len(nums)\n",
    "         \n",
    "         nums.sort()\n",
    "         if l < nums[0]:\n",
    "             return l\n",
    "\n",
    "         for i in range(len(nums)):\n",
    "              if nums[i] == 0:\n",
    "                 continue\n",
    "              elif i > 0 and l - i <= nums[i] and l - i > nums[i - 1]:\n",
    "                    return l - i\n",
    "              elif i == 0 and l - i == nums[i]:\n",
    "                  return l - i\n",
    "                                  \n",
    "         return -1\n",
    "         \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        left,right=-1,n+1\n",
    "        while left<=right:\n",
    "            mid=(left+right)>>1\n",
    "            if(t:=n-bisect_left(nums,mid))==mid:\n",
    "                return mid\n",
    "            elif(t<mid):\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "            \n",
    "        return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        a = 0\n",
    "        b = n\n",
    "        i = (b-a+1) // 2\n",
    "        while a < b and 0 < i <= n:\n",
    "            if (nums[n-i-1] < i and nums[n-i] >= i) or (i == n and nums[0] >= i):\n",
    "                break\n",
    "            elif nums[n-i-1] >= i:\n",
    "                a = i\n",
    "                i += (b-a+1) // 2\n",
    "            elif nums[n-i] < i and b != i:\n",
    "                b = i\n",
    "                i -= (b-a+1) // 2\n",
    "            else:\n",
    "                i = -1\n",
    "                break\n",
    "        if a >= b or i > n or i == 0:\n",
    "            i = -1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: list[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        t = 0\n",
    "        for i in nums:\n",
    "            if i == t:\n",
    "                return -1\n",
    "            if i > t:\n",
    "                t += 1\n",
    "        return t \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1, len(nums)+1):\n",
    "            k = 0\n",
    "            for j in nums:\n",
    "                if j >= i:\n",
    "                    k = k + 1\n",
    "            if k == i:\n",
    "                return k\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n+1):\n",
    "            count = 0\n",
    "            for j in range(n):\n",
    "                if nums[j] >= i:\n",
    "                    count += 1\n",
    "            if count == i:\n",
    "                return i\n",
    "        return -1 \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if len([k for k in nums if k >= i]) == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            if nums[i - 1] >= i and (i == len(nums) or nums[i] < i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        ans = [0 for _ in range(1001)]\n",
    "        \n",
    "        for i in nums:\n",
    "            ans[i] += 1\n",
    "       \n",
    "        for j in range(1001, -1,-1):\n",
    "            if j == sum(ans[j:]):\n",
    "                return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def specialArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        nums_set = set(nums)\n",
    "        sort_list = sorted(nums)\n",
    "        for i in nums_set:\n",
    "            si = sort_list.index(i)\n",
    "            x = length - si\n",
    "            if si == 0 and x <= i:\n",
    "                return x\n",
    "            if sort_list[si-1] < x <= i:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        k = 0\n",
    "        for i in range(n + 1):\n",
    "            for j in nums:\n",
    "                if(i <= j):\n",
    "                    k += 1\n",
    "            if(i == k):\n",
    "                break\n",
    "            k = 0\n",
    "            if( i == n):\n",
    "                k = -1\n",
    "        return k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        max_n = max(nums)\n",
    "        if max_n == 0:\n",
    "            return -1\n",
    "        arr = [0] * (max_n + 1)\n",
    "        for n in nums:\n",
    "            for i in range(0, n+1):\n",
    "                arr[i] += 1\n",
    "        for j in range(len(arr)):\n",
    "            if j == arr[j]:\n",
    "                return j\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            start, end = 0, len(nums) - 1\n",
    "            mid = (start + end) >> 1\n",
    "            while start <= end:\n",
    "                if nums[mid] < i:\n",
    "                    start = mid + 1\n",
    "                else:\n",
    "                    end = mid - 1\n",
    "                mid = (start + end )>> 1\n",
    "            if len(nums[start:]) == i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        c=0\n",
    "        for i in range(1,n+1): #0,1,2\n",
    "            for j in sorted(nums, reverse=True):\n",
    "                if j>=i:\n",
    "                    c+=1\n",
    "            if i==c:\n",
    "                return i\n",
    "                break\n",
    "            else:\n",
    "                c=0\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    " \n",
    "        n = max(nums)\n",
    "        for j in range(n+1):\n",
    "            res = 0\n",
    "            for i in nums:\n",
    "                if i >= j:\n",
    "                    res += 1\n",
    "            if res == j:return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        left, right = 1, len(nums)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1 #左边的运算数的各二进位全部右移若干位\n",
    "            if nums[mid - 1] >= mid:\n",
    "                if mid == len(nums) or nums[mid] < mid:\n",
    "                    return mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        k=len(nums)\n",
    "        n=k\n",
    "        if k<=nums[0]:\n",
    "            return k\n",
    "        while k>0:\n",
    "            k=k-1\n",
    "            if nums[n-k-1]<k<=nums[n-k]:\n",
    "                return k\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        max_n = max(nums)\n",
    "        if max_n == 0:\n",
    "            return -1\n",
    "        arr = [0] * (max_n + 1)\n",
    "        for n in nums:\n",
    "            for i in range(0, n+1):\n",
    "                arr[i] += 1\n",
    "        for j in range(len(arr)):\n",
    "            if j == arr[j]:\n",
    "                return j\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        #暴力\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for x in range(1001):\n",
    "            if x > nums[-1]:\n",
    "                break\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if nums[j] >= x:\n",
    "                    cnt += 1\n",
    "            if cnt == x:\n",
    "                return cnt\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        l, r = 1, len(nums)\n",
    "        while l <= r:\n",
    "            m = (l + r) // 2\n",
    "            if nums[m-1] >= m:\n",
    "                if m == len(nums) or nums[m] < m:\n",
    "                    return m\n",
    "                else:\n",
    "                    l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        ans = [0 for _ in range(1001)]\n",
    "        \n",
    "        for i in nums:\n",
    "            ans[i] += 1\n",
    "       \n",
    "        for j in range(1001, -1,-1):\n",
    "            if j == sum(ans[j:]):\n",
    "                return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        # minx = min(nums) - 1 if min(nums) != 0 else 1\n",
    "        # maxx = max(nums) + 1\n",
    "        # countmax = 0\n",
    "        # for i in range(minx,maxx):\n",
    "        #     count = 0\n",
    "        #     for j in nums:\n",
    "        #         if j >= i:\n",
    "        #             count += 1\n",
    "        #     if count >= countmax:\n",
    "        #         countmax = count\n",
    "        # if countmax != 0:\n",
    "        #     return countmax\n",
    "        # else:\n",
    "        #     return -1\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n+1):\n",
    "            if nums[i-1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        if nums[n-1] >= n:\n",
    "            return n\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if nums[i-1] >= i and nums[i] < i:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        l = len(nums)\n",
    "        for i in range(1, l + 1):\n",
    "            if l - bisect_left(nums, i) == i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnter = Counter(nums)\n",
    "        for i in range(1, n+1):\n",
    "            cnt = 0\n",
    "            for num in nums:\n",
    "                if num >= i:\n",
    "                    cnt += 1\n",
    "            if cnt == i:\n",
    "                return i\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = max(nums)\n",
    "        mid = left + (right - left)//2\n",
    "        nums.sort()\n",
    "        def getRes(mid):\n",
    "            res = 0\n",
    "            for i in range(0, len(nums)):\n",
    "                if mid <= nums[i]:\n",
    "                    res = res + 1\n",
    "            return res >= mid\n",
    "        \n",
    "        while left <= right:\n",
    "            if getRes(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "            mid = left + (right - left)//2\n",
    "        \n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if left - 1 <= i:\n",
    "                res = res + 1\n",
    "        \n",
    "        return left - 1 if left - 1 == res else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        def jugement(pos, nums):\n",
    "            i, j = 0, len(nums)\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                if nums[mid] < pos: i = mid + 1\n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                if nums[k] >= pos:\n",
    "                    return len(nums) - k\n",
    "            return len(nums)\n",
    "\n",
    "        def binarySearch(i, j, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i+j) >> 1\n",
    "                cnt = jugement(mid, nums)\n",
    "                if cnt > mid: i = mid + 1\n",
    "                else: j = mid\n",
    "            for k in range(i, j+1):\n",
    "                cnt = jugement(k, nums)\n",
    "                if cnt == k:\n",
    "                    return k\n",
    "            return -1\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        return binarySearch(0, max(nums), nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)+1,0,-1):\n",
    "            count=0\n",
    "            for j in nums:\n",
    "                if j>=i:\n",
    "                    count+=1\n",
    "            if count==i:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        lst = [0] * 101\n",
    "        for n in nums:\n",
    "            for i in range(min(n + 1, 101)):\n",
    "                lst[i] += 1\n",
    "        for i, n in enumerate(lst):\n",
    "            if i == n:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        # 给nums从大到小排序\n",
    "        nums.sort(reverse=True)\n",
    "        if nums[0] == 0:\n",
    "            return -1\n",
    "        # 通过+1达到防止数组越界的目的\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if  i <= nums[i-1] and (i==len(nums) or i > nums[i]):\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def specialArray(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        nums_set = set(nums)\n",
    "        sort_list = sorted(nums)\n",
    "        for i in nums_set:\n",
    "            si = sort_list.index(i)\n",
    "            x = length - si\n",
    "            if si == 0 and x <= i:\n",
    "                return x\n",
    "            if sort_list[si-1] < x <= i:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)+1):\n",
    "            if nums[len(nums)-i] >= i and i < len(nums) and nums[len(nums)-i-1] < i:\n",
    "                return i\n",
    "            elif i == len(nums) and nums[0] >= len(nums):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "         l = len(nums)\n",
    "         \n",
    "        \n",
    "         nums.sort()\n",
    "         if l < nums[0]:\n",
    "             return l\n",
    "\n",
    "         for i in range(len(nums)):\n",
    "              if nums[i] == 0:\n",
    "                 continue\n",
    "              elif i > 0 and l - i <= nums[i] and l - i > nums[i - 1]:\n",
    "                    return l - i\n",
    "              elif i == 0 and l - i == nums[i]:\n",
    "                  return l\n",
    "                                  \n",
    "         return -1\n",
    "         \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums)):\n",
    "            if i-1>=0:\n",
    "                if nums[i]>=len(nums)-i and nums[i-1]<len(nums)-i:\n",
    "                    return len(nums[i:])\n",
    "            else:\n",
    "                if nums[i]>=len(nums)-i:\n",
    "                    return len(nums[i:])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def specialArray(self, nums: List[int]) -> int:\r\n",
    "        for i in range(len(nums)+1):\r\n",
    "            temp = sorted(nums + [i-0.5])\r\n",
    "            if i == len(nums) - temp.index(i-0.5):\r\n",
    "                return i\r\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        for x in range(len(nums) + 1):\n",
    "            cnt = sum([x <= num for num in nums])\n",
    "            if cnt == x:\n",
    "                return x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "         l = len(nums)\n",
    "         \n",
    "        \n",
    "         nums.sort()\n",
    "         if l < nums[0]:\n",
    "             return l\n",
    "\n",
    "         for i in range(len(nums)):\n",
    "              if nums[i] == 0:\n",
    "                 continue\n",
    "              elif i > 0 and l - i <= nums[i] and l - i > nums[i - 1]:\n",
    "                    return l - i\n",
    "              elif i == 0 and l - i == nums[i]:\n",
    "                  return l - i\n",
    "                                  \n",
    "         return -1\n",
    "         \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        if 0 < n - i and n - i <= nums[0]:\n",
    "            return n - i\n",
    "        i = 1\n",
    "        while i < n and nums[i]==nums[i-1]:\n",
    "            i = i + 1\n",
    "        while i < n:\n",
    "            if(nums[i - 1] < n - i and n - i <= nums[i]):\n",
    "                return n - i\n",
    "            i = i + 1\n",
    "            while i < n and nums[i]==nums[i-1]:\n",
    "                 i = i + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        ans = [0 for _ in range(1001)]\n",
    "        \n",
    "        for i in nums:\n",
    "            ans[i] += 1\n",
    "       \n",
    "        for j in range(1000):\n",
    "            if j == sum(ans[j:]):\n",
    "                return j\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        print(nums)\n",
    "        ans=0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>=i+1:\n",
    "                ans=i+1\n",
    "            elif nums[i]==i:\n",
    "                return -1\n",
    "            else:\n",
    "                break\n",
    "        return ans if ans!=0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        max_n = max(nums)\n",
    "        if max_n == 0:\n",
    "            return -1\n",
    "        arr = [0] * (max_n + 1)\n",
    "        for n in nums:\n",
    "            for i in range(0, n+1):\n",
    "                arr[i] += 1\n",
    "        for j in range(len(arr)):\n",
    "            if j == arr[j]:\n",
    "                return j\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: list[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        t = 0\n",
    "        for i in nums:\n",
    "            if i == t:\n",
    "                return -1\n",
    "            if i > t:\n",
    "                t += 1\n",
    "        return t \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialArray(self, nums: List[int]) -> int:\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        for i in range(1, n + 1):\n",
    "            if nums[i - 1] >= i and (i == n or nums[i] < i):\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
